package com.example.algorithm.tree.heap;

public class HeapSort {
    /**
     * 判断i处小于j处
     *
     * @param heap
     * @param i
     * @param j
     * @return
     */
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    /**
     * 交换heap数组i处和j处的值
     *
     * @param heap
     * @param i
     * @param j
     */
    private static void exch(Comparable[] heap, int i, int j) {
        Comparable temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }


    /**
     * 根据原数组，构建堆数组
     *
     * @param source
     * @param heap
     */
    private static void createHeap(Comparable[] source, Comparable[] heap) {
        //把source的元素拷贝到heap中,heap中元素形成一个无序的堆
        System.arraycopy(source, 0, heap, 1, source.length);
        //对堆中的元素做下沉调整,从长度的一半处向索引处扫描
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap, i, heap.length-1);
        }
    }

    private static void sink(Comparable[] heap, int target, int range) {
        while (2 * target <= range) {
            int max;
            if (2 * target + 1 <= range) {
                if (less(heap, 2 * target, 2 * target + 1)) {
                    max = 2 * target + 1;
                } else {
                    max = 2 * target;
                }
            } else {
                max = 2 * target;
            }

            if (!less(heap,target,max)){
                break;
            }

            exch(heap,target,max);
            target = max;
        }
    }

    public static void sort(Comparable[] source){
        //构建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source,heap);
        //定义一个遍历，记录未排序中最大索引
        int N = heap.length - 1;
        //循环交换1和未排序最大索引元素
        while (N!=1){
            //交换元素
            exch(heap,1,N);
            //排除交换后元素所在最大索引调整
            N--;
            //需要对索引1处的元素下沉调整
            sink(heap,1,N);
        }

        System.arraycopy(heap,1,source,0,source.length);

    }


}
